﻿#include<stdio.h>

typedef int Datatype;

//交换
void swap(Datatype* x, Datatype* y)
{
	Datatype temp = *x;
	*x = *y;
	*y = temp;
}

//向下调整-升序
void Adjustdown_up(Datatype* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//升序--使用大堆，将元素建堆后堆顶元素为最大元素，所以每次将堆顶元素与最后位置元素交换，既可以使得数组进行升序排序。
void Headsort_Up(Datatype* arr,int n)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown_up(arr, n, i);
	}

	int end = n - 1;
	//出堆，堆顶的元素为最大值
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		Adjustdown_up(arr, end, 0);
		end--;
	}
}

//-------------------------------------------------------------------------------------------------------------------------------------------------


//向下调整-降序
void Adjustdown_down(Datatype* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//降序--使用小堆，将元素建堆后堆顶元素为最小元素，所以每次将堆顶元素与最后位置元素交换，既可以使得数组进行降序排序。
void Headsort_Down(Datatype* arr, int n)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown_down(arr, n, i);
	}

	int end = n - 1;
	//出堆，堆顶的元素为最大值
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		Adjustdown_down(arr, end, 0);
		end--;
	}
}
